package leetcode.year2021.month10;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

public class _16_01Permute46 {
  // 46 全排列
  // 思路： 使用回溯的方法
  public List<List<Integer>> permute(int[] nums) {
    int n = nums.length;

    List<List<Integer>> ans = new ArrayList<>();

    List<Integer> integerNums = new ArrayList<>(nums.length);
    for (int num : nums) {
      integerNums.add(num);
    }

    dfs(ans,integerNums,n,0);
    return ans;
  }

  private void dfs(List<List<Integer>> ans, List<Integer> integerNums, int n, int first) {
    if (n == first){
      ans.add(new ArrayList<>(integerNums));
      return;
    }

    for (int i = first; i < n; i++) {
      Collections.swap(integerNums, first, i);
      dfs(ans,integerNums,n,first+1);
      Collections.swap(integerNums, i, first);
    }
  }

  /**
   * 46. 全排列
   * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
   *
   *
   *
   * 示例 1：
   *
   * 输入：nums = [1,2,3]
   * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
   * 示例 2：
   *
   * 输入：nums = [0,1]
   * 输出：[[0,1],[1,0]]
   * 示例 3：
   *
   * 输入：nums = [1]
   * 输出：[[1]]
   *
   *
   * 提示：
   *
   * 1 <= nums.length <= 6
   * -10 <= nums[i] <= 10
   * nums 中的所有整数 互不相同
   */
}
